package leetcode.biweekly.week97;

//Solution4Test
public class Solution4 {

	int[] p;
	int[] s;

	public void init(int size) {
		p = new int[size];
		s = new int[size];
		for (int i = 0; i < p.length; i++) {
			p[i] = i;
		}
	}

	public void union(int a, int b) {
		if (find(a) == find(b)) {
			return;
		}
		p[find(a)] = find(b);
		s[find(b)] = s[find(b)] | s[find(a)];
	}

	public int find(int id) {
		if (p[id] != id) {
			p[id] = this.find(p[id]);
		}
		return p[id];
	}

	public boolean isSameSet(int a, int b) {
		return find(a) == find(b);
	}

	public int index(int i, int j, int n) {
		return i * n + j;
	}

	public boolean isPossibleToCutPath(int[][] grid) {
		int[] direction = new int[] { -1, -1, -1, 0, -1, 1, 0, -1, 0, 1, 1, -1, 1, 0, 1, 1 };
		int m = grid.length, n = grid[0].length;
		if (m == 1) {
			return n != 2;
		}
		int total = m * n;
		init(total);
		for (int i = 0; i < m; i++) {
			s[index(i, 0, n)] = 1 << 3;
			s[index(i, n - 1, n)] = 1 << 1;
		}
		for (int i = 1; i < n - 1; i++) {
			s[index(0, i, n)] = 1;
			s[index(m - 1, i, n)] = 1 << 2;
		}
		s[0] = 0;
		s[index(m - 1, n - 1, n)] = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int cur = grid[i][j];
				if (cur == 0) {
					for (int k = 0; k < direction.length; k += 2) {
						int x = i + direction[k], y = j + direction[k + 1];
						if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0) {
							union(index(i, j, n), index(x, y, n));
						}
					}
				}
			}
		}
		s[0] = 0;
		s[index(m - 1, n - 1, n)] = 0;
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				int cur = grid[i][j];
				if (f(s[find(index(i, j, n))])) {
					return true;
				}
				if (cur == 1) {
					int ss = 0;
					for (int k = 0; k < direction.length; k += 2) {
						int x = i + direction[k], y = j + direction[k + 1];
						if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 0) {
							ss |= s[find(index(x, y, n))];
						}
					}
					ss |= s[index(i, j, n)];
					if (f(ss)) {
						return true;
					}
				}
			}
		}
		return false;
	}

	private boolean f(int ss) {
		return ((ss & 0b1001) == 0b1001) || ((ss & 0b1010) == 0b1010) || ((ss & 0b0110) == 0b0110);
	}

}
